package two.chapter_1.c1_4;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

import java.util.Arrays;

public class ThreeSum {


    public static void main(String [] args){
        int MAX=1000000;
        int N=10000;
        final int[] a=new int[N];
        for (int i=0;i<N;i++){
            a[i]=StdRandom.uniform(-MAX,MAX);
        }
        new Thread(new Runnable() {
            @Override
            public void run() {
                Stopwatch stopwatch=new Stopwatch();
                StdOut.println("count:"+threeSum(a));
                StdOut.println(stopwatch.elapseTime());//276.8s
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                Stopwatch stopwatch2=new Stopwatch();
                StdOut.println("count:"+threeSumFast(a));
                StdOut.println(stopwatch2.elapseTime());//4.2s
            }
        }).start();

    }

    /**
     * 时间复杂度   N^3
     * @param a
     * @return
     */
    public static int  threeSum(int[] a){
        int count=0;
        for (int i=0;i<a.length;i++){
            for (int j=i+1;j<a.length;j++){
                for (int k=j+1;k<a.length;k++) {
                    if ((long)a[i] + a[j]+a[k] == 0) {  //较大的int值相加可能会溢出，所以需要将int转为long
                        count++;
                    }
                }
            }
        }
        return count;
    }

    /**
     * 时间复杂度  N^2*logN
     * @param a
     * @return
     */
    public static int threeSumFast(int[] a){
        int count=0;
        Arrays.sort(a);//归并排序  NlogN

        for (int i=0;i<a.length;i++){
            for (int j=i+1;j<a.length;j++) {
                if (BinarySearch.rank(-a[i]-a[j], a) > j) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * ~N^2
     * @param sortedArray
     * @return
     */
    public static int threeSumFastSorted(int[] sortedArray){
        int count = 0;
        int N=sortedArray.length;

        for (int i=0;i<N;i++) {
            int a=sortedArray[i];
            int lo = i+1;
            int hi = N - 1;
            while (lo < hi) {
                if (sortedArray[lo] + sortedArray[hi] +a> 0) {
                    hi--;
                } else if (sortedArray[lo] + sortedArray[hi]+a < 0) {
                    lo++;
                } else {
                    count++;
                    lo++;
                    hi--;
                }
            }
        }
        return count;
    }
}
